--[[
	https://blog.csdn.net/f81892461/article/details/8578224
	bitmap是一个十分有用的结构。所谓的Bit-map就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。

	lua不能分配内存只能操作64位数据的位操作， 所以只能对 小于62的数据起作用
	
--]]
local string = string
local string_len = string.len
local string_byte = string.byte
local math = math


local Bitmap = {}

function Bitmap.new(...)
	local instance = setmetatable({}, {__index=Bitmap})
	instance:ctor(...)
	return instance
end

function Bitmap:ctor(arr, max_bit)
	print("max_bit", max_bit)
	self.arr = arr
	self.max_bit = max_bit
	self.data = 0 --lua的number类型 64位
	for k, v in pairs(arr) do
		self:set(v)
	end
end

--设置第i位的值为1
function Bitmap:set(i)
	self.data = self.data | (1 << i)
end

--取第i位是1还是0
function Bitmap:get(i)
	local num = self.data & (1 << i)
	if num > 0 then
		return 1
	end
	return 0
end

--第i位对应的数据
function Bitmap:getData(i)
	return i
end


function Bitmap:empty()
	if self.count > 0 then
		return false
	end
	return true
end

function Bitmap:print()
	for i=0, self.max_bit do
		if self:get(i) == 1 then
			print(self:getData(i))
		end
	end
end

------------------------------------------------------------------
--测试
------------------------------------------------------------------
if arg and arg[0] == "bitmap.lua" then
	local arr = {1,3,13,100,1,2,4,5, 62, 63,}
	local bitmap = Bitmap.new(arr, 103)
	bitmap:print()
	print("_______")
	print("_______", bitmap:get(100))

end



return Bitmap

